`
https://leetcode.cn/problems/interleaving-string/
`

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
  const m = s1.length, n = s2.length, t = s3.length;
  if (m + n !== t) return false;

  // 选择较短的字符串作为滚动方向，空间复杂度 O(min(m,n))
  const [A, B] = m <= n ? [s1, s2] : [s2, s1];
  const lenA = A.length, lenB = B.length;

  // 使用一维DP数组
  const dp = new Array(lenB + 1).fill(false);

  // 初始化：处理空字符串的情况
  dp[0] = true;
  for (let j = 1; j <= lenB; j++) {
    dp[j] = dp[j - 1] && B[j - 1] === s3[j - 1];
  }

  // 动态规划主循环
  for (let i = 1; i <= lenA; i++) {
    // 处理当前行第一列（相当于二维数组中的 dp[i][0]）
    dp[0] = dp[0] && A[i - 1] === s3[i - 1];

    for (let j = 1; j <= lenB; j++) {
      const k = i + j; // s3中的位置
      const fromA = dp[j] && A[i - 1] === s3[k - 1];       // 来自A的路径
      const fromB = dp[j - 1] && B[j - 1] === s3[k - 1];     // 来自B的路径
      dp[j] = fromA || fromB; // 更新当前状态
    }
  }

  return dp[lenB];
};